/**
 * 给你两个整数，被除数 dividend 和除数 divisor。将两数相除，要求 不使用 乘法、除法和取余运算。
 * 整数除法应该向零截断，也就是截去（truncate）其小数部分。例如，8.345 将被截断为 8 ，-2.7335 将被截断至 -2 。
 * 返回被除数 dividend 除以除数 divisor 得到的 商 。
 * 注意：假设我们的环境只能存储 32 位 有符号整数，其数值范围是 [−231,  231 − 1] 。本题中，如果商 严格大于 231 − 1
 * 则返回 231 − 1 ；如果商 严格小于 -231 ，则返回 -231 。
 *
 * 示例 1:
 * 输入: dividend = 10, divisor = 3
 * 输出: 3
 * 解释: 10/3 = 3.33333.. ，向零截断后得到 3 。
 *
 * 示例 2:
 * 输入: dividend = 7, divisor = -3
 * 输出: -2
 * 解释: 7/-3 = -2.33333.. ，向零截断后得到 -2 。
 *
 * 提示：
 * -231 <= dividend, divisor <= 231 - 1
 * divisor != 0
 */

/**
 * 除法运算, 我们可以知道所谓的除法其实就是在被除数上一步一步的减去除数, 减去了几次为零, 这个数减一就是最后的结果
 * 基于这个方法的暴力方法, 时间复杂度为 : O(n), 这个时间复杂度明显不是我们想要的, 本题会超时, 所以我们要优化此暴力解法
 * 如果一个一个的除数相加不能满足我们的需要, 那我们尝试下每次给这个数乘二相加呢?
 * 我们可以想到如果 60 > 8 所以结果肯定大于 1, 将除数乘 2, 60 > 16, 那么结果就大于 2了
 * 60 > 32 ==> 4   60 < 64 ==> 8
 * 所以结果就在 4 和 8 之间
 * 怎么将该数更精进呢, 我们可以让被除数减去之前求得最大的除数
 * 60 - 32 = 28     28 > 16 && 28 < 32  ==> 2 -- 4
 * 28 - 16 = 12     12 > 8  && 12 < 16  ==> 1 -- 2
 * 12 - 8 = 4       4 < 8   ==>  0
 * 最后结果 : 4 + 2 + 1 = 7
 *
 * 60 / 8 = 7  ==> (60 - 28 - 16 - 8) / 8 + 4 + 2 + 1 = 7
 * 这里我们可以看出我们需要再每次的被除数 大于 除数 时进行精确结果
 *
 * 这里我们注意处理结果越界的情况, 对于 int 类型, 我们一般将他们转化我 long 类型进行处理
 * 时间复杂度 : O(log(n))
 * 空见复杂度 : O(1)
 */

public class Main {
    public int divide(int dividend, int divisor) {

        // 这里我们需要特别判断一下 除数 = 1 的情况, 因为当被除数为 Integer.MIN_VALUE时,
        // 因为正数的最大值要比负数转化成正数的最大值小一, 所以我们后面对 count << 1 的时候一定
        // 会使 count > -Integer.MIN_VALUE, 也就大于正数的最大范围, 导致结果越界
        if (divisor == 1) {
            return dividend;
        }

        // 当除数为负数, 且被除数为最小值时, 我们求得结果时让结果越界, 并且题目也规定了返回整数的最大值
        if (divisor == -1 && dividend == Integer.MIN_VALUE) {
            return Integer.MAX_VALUE;
        }

        if (dividend < 0 && divisor < 0) {

            // 如果两个都为负数, 结果为正
            return dfs(-(long)dividend, -(long)divisor);

        } else if (dividend < 0 || divisor < 0) {

            // 如果有一个为负数, 那么结果为负
            return -dfs(Math.abs((long)dividend),
                    Math.abs((long)divisor));

        } else {

            // 剩下的就是两个都为正数
            return dfs((long)dividend, (long)divisor);

        }
    }

    private int dfs (long dividend, long divisor) {

        // 当被除数小于除数时, 没得加了, 返回0
        if (dividend < divisor) {
            return 0;
        }

        // 记录最大的除数
        long sum = divisor;

        // 记录到最大除数用了多少个 除数相加
        int count = 1;


        // 我们要求得最大的除数
        while (dividend >= sum) {
            sum <<= 1;
            count <<= 1;
        }

        // 这里我们已经求得大于被除数的除数了, 所以要求得最大的除数, 要向后退一个
        // 注意这里一定要使用 >>> 无符号右移,
        // 因为当 被除数取 最小的整数时, count一定会越界(变为负数), 这时候如果我们还用 >> 就会补充符号位 1 ,
        // 所以我们要用无符号右移, 最高位补 0, 才能得到正确结果
        sum >>>= 1;
        count >>>= 1;

        // 这里要让结果一致累加起来, 并不断地减少被减数, 来精确结果
        return count + dfs(dividend - sum, divisor);
    }

    public static void main(String[] args) {
        Main test = new Main();
        test.divide(-2147483648, 2);
    }
}